package 蓝桥杯算法;

public class day08 {
    public static void main(String[] args) {
        day08 a=new day08();
        String s="aa dd ffs aaaa";
        System.out.println( a.reverseWords(s));
        String c="asdcdsg";
        System.out.println(a.reverseWord1(c,2));
        String y="asdcccc";
        String x="dc";
        System.out.println(a.strStr(y,x));
    }
    public String reverseWords(String s){
        StringBuilder sb=removeSpace(s);
        reverseString(sb,0,sb.length()-1);
        resverseEachWord(sb);
        return sb.toString();
    }
    public StringBuilder removeSpace(String s){
        int start=0;
        int end=s.length()-1;
        while(s.charAt(start)==' '){
            start++;
        }
        while(s.charAt(end)==' '){
            end--;
        }
        StringBuilder sb=new StringBuilder();
        while(start<=end){
            char c=s.charAt(start);
            if(c!=' '||sb.charAt(sb.length()-1)!=' '){//确保空格键只有一个
                sb.append(c);
            }
            start++;
        }
        return sb;
    }
    public void reverseString(StringBuilder sb,int start,int end){
        while(start<end){
            char temp=sb.charAt(start);
            sb.setCharAt(start,sb.charAt(end));//集合的交换
            sb.setCharAt(end,temp);
            start++;
            end--;
        }
    }
    public void resverseEachWord(StringBuilder sb){
        int start=0;
        int end=1;
        int n=sb.length();
        while(start<n){
            while(end<n&&sb.charAt(end)!=' '){
                end++;//找到空格的位置
            }
            reverseString(sb,start,end-1);//减一是因为该位置是空格
            start=end+1;
            end=start+1;
        }
    }

    public String reverseWord1(String s,int k){//右旋转字符串
        StringBuilder sb=new StringBuilder();
        char[] array=s.toCharArray();
        for(int i=0;i<array.length;i++){
            sb.append(array[i]);
        }
        reverseString(sb,0,sb.length()-1);
        reverseString(sb,0,k-1);
        reverseString(sb,k,sb.length()-1);
        return sb.toString();
    }
    public StringBuilder reverseString1(StringBuilder sb,int start,int end){
        while(start<end){
            char temp=sb.charAt(start);
            sb.setCharAt(start,sb.charAt(end));
            sb.setCharAt(end,temp);
            start++;
            end--;
        }
        return sb;
    }
    public int strStr(String haystack,String needle) {//暴力算法
        int n=haystack.length();
        int m=needle.length();
        char[] arr1=haystack.toCharArray();
        char[] arr2=needle.toCharArray();
       for(int i=0;i<n-m+1;i++){
           int a=i;
           int b=0;
           while(b<m&&arr1[a]==arr2[b]){
               a++;
               b++;
           }
           if(b==m){
               return i;
           }
       }
       return -1;
    }
}
